Search for: All records

Abstract The Ising model provides a natural mapping for many computationally hard combinatorial optimization problems (COPs). Consequently, dynamical system-inspired computing models and hardware platforms that minimize the Ising Hamiltonian, have recently been proposed as a potential candidate for solving COPs, with the promise of significant performance benefit. However, prior work on designing dynamical systems as Ising machines has primarily considered quadratic interactions among the nodes. Dynamical systems and models considering higher order interactions among the Ising spins remain largely unexplored, particularly for applications in computing. Therefore, in this work, we propose Ising spin-based dynamical systems that consider higher order (> 2) interactions among the Ising spins, which subsequently, enables us to develop computational models to directly solve many COPs that entail such higher order interactions (i.e., COPs on hypergraphs). Specifically, we demonstrate our approach by developing dynamical systems to compute the solution for the Boolean NAE-K-SAT (K ≥ 4) problem as well as solve the Max-K-Cut of a hypergraph. Our work advances the potential of the physics-inspired ‘toolbox’ for solving COPs. 

Nonlinear dynamical systems such as coupled oscillators are being actively investigated as Ising machines for solving computationally hard problems in combinatorial optimization. Prior works have established the equivalence between the global minima of the cost function describing the coupled oscillator system and the ground state of the Ising Hamiltonian. However, the properties of the oscillator Ising machine (OIM) from a nonlinear control viewpoint, such as the stability of the OIM solutions, remain unexplored. Therefore, in this work, using nonlinear control-theoretic analysis, we (i) identify the conditions required to ensure the functionality of the coupled oscillators as an Ising machine, (ii) show that all globally optimal phase configurations may not always be stable, resulting in some configurations being more favored over others and, thus, creating a biased OIM, and (iii) elucidate the impact of the stability of locally optimal phase configurations on the quality of the solution computed by the system. Our work, fostered through the unique convergence between nonlinear control theory and analog systems for computing, provides a new toolbox for the design and implementation of dynamical system-based computing platforms. 

Abstract Realizing compact and scalable Ising machines that are compatible with CMOS-process technology is crucial to the effectiveness and practicality of using such hardware platforms for accelerating computationally intractable problems. Besides the need for realizing compact Ising spins, the implementation of the coupling network, which describes the spin interaction, is also a potential bottleneck in the scalability of such platforms. Therefore, in this work, we propose an Ising machine platform that exploits the novel behavior of compact bi-stable CMOS-latches (cross-coupled inverters) as classical Ising spins interacting through highly scalable and CMOS-process compatible ferroelectric-HfO 2 -based Ferroelectric FETs (FeFETs) which act as coupling elements. We experimentally demonstrate the prototype building blocks of this system, and evaluate the scaling behavior of the system using simulations. Our work not only provides a pathway to realizing CMOS-compatible designs but also to overcoming their scaling challenges. 

Abstract Noise is expected to play an important role in the dynamics of analog systems such as coupled oscillators which have recently been explored as a hardware platform for application in computing. In this work, we experimentally investigate the effect of noise on the synchronization of relaxation oscillators and their computational properties. Specifically, in contrast to its typically expected adverse effect, we first demonstrate that a common white noise input induces frequency locking among uncoupled oscillators. Experiments show that the minimum noise voltage required to induce frequency locking increases linearly with the amplitude of the oscillator output whereas it decreases with increasing number of oscillators. Further, our work reveals that in a coupled system of oscillators—relevant to solving computational problems such as graph coloring, the injection of white noise helps reduce the minimum required capacitive coupling strength. With the injection of noise, the coupled system demonstrates frequency locking along with the desired phase-based computational properties at 5 × lower coupling strength than that required when no external noise is introduced. Consequently, this can reduce the footprint of the coupling element and the corresponding area-intensive coupling architecture. Our work shows that noise can be utilized as an effective knob to optimize the implementation of coupled oscillator-based computing platforms.